1. Field of the Invention
The present invention relates to a sort processing apparatus and, more particularly, to a sort processing apparatus having a pipeline arrangement for performing merge sort of two sets of input data in accordance with a two-way merge sort algorithm.
2. Description of the Related Art
In a conventional sort processing apparatus for performing sort processing in accordance with a two-way merge sort algorithm, a hardware arithmetic circuit having an arrangement shown in FIG. 1 is used to realize a high speed operation of the sort processing. That is, an apparatus shown in FIG. 1 is arranged such that sort cells 1-1, 1-2 . . . . 1-n are connected to each other in series, and each of the sort cells 1-1, 1-2, . . . 1-n outputs a data row aligned by performing merge sort of two sets of input data.
Each of the sort cells 1-1, 1-2, . . . 1-n consists of a buffer memory for temporarily storing input data and a sort controller for sorting the data stored in the buffer memory. That is, the first sort cell 1-1 consists of a sort controller 11-1 and a buffer memory 12-1, the second sort cell 1-2 consists of a sort controller 11-2 and a buffer memory 12-2, and the nth sort cell 1-n consists of a sort controller 11-n and a buffer memory 12-n. Each of the sort controllers has a control circuit and directly inputs a memory address to a corresponding buffer memory to access it.
At this time, according to the nature of the two-way merge sort algorithm, the first sort cell 1-1 requires a buffer memory capacity twice a data length to be sorted (e.g., a record length), the second sort cell 1-2 requires a buffer memory capacity four times the data length, and the nth sort cell 1-n requires a buffer memory capacity 2.sup.n times the data length.
In the two-way merge sort, the first sort cell 1-1 sequentially stores data in the buffer memory 12-1 in units of two data from the start data of input data rows to sort each of sets of data, the second sort cell 1-2 stores the data rows sorted by the first sort cell 1-1 in the buffer memory 12-2 in units of two sets of rows to sort two sets of data rows (four data), and the third sort cell stores the data rows sorted by the second sort cell 1-2 in buffer memories in units of two sets of rows to sort two sets of data rows (eight data).
In the sort processing apparatus, for performing two-way merge sort, having the pipeline shown in FIG. 1, the buffer memory of the last sort cell requires a large memory capacity, but a small memory capacity is enough for the buffer memory of the first sort cell.
However, in practice, since types of semiconductor memory chips used as a buffer memory are limited, a memory suitable for a memory capacity of each of buffer memories cannot be easily prepared for all the sort cells. For this reason, conventionally, a memory chip having a relatively large memory capacity is arranged for each of all the sort cells. In this case, although there is no problem in the last sort cell, most part of the memory capacity of the memory chip is not used to be wasted in the first sort cell.
In addition, since the sort controllers 11-1 through 11-n access the buffer memories 12-1 through 12-n through different memory buses, respectively, when these sort controllers 11-1 through 11-n are to be formed as a one-chip LSI, a large number of input/output pins are required to independently lead the memory buses from the chip. For this reason, the one-chip LSI cannot be easily realized.